﻿// 1076. 迷宫问题.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <map>
#include <queue>

using namespace std;

/*
https://www.acwing.com/problem/content/1078/

给定一个 n×n 的二维数组，如下所示：

int maze[5][5] = {
0, 1, 0, 0, 0,
0, 1, 0, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
};
它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。

数据保证至少存在一条从左上角走到右下角的路径。

输入格式
第一行包含整数 n。

接下来 n 行，每行包含 n 个整数 0 或 1，表示迷宫。

输出格式
输出从左上角到右下角的最短路线，如果答案不唯一，输出任意一条路径均可。

按顺序，每行输出一个路径中经过的单元格的坐标，左上角坐标为 (0,0)，右下角坐标为 (n−1,n−1)。

数据范围
0≤n≤1000
输入样例：
5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
输出样例：
0 0
1 0
2 0
2 1
2 2
2 3
2 4
3 4
4 4
*/

const int N = 1010;
int gra[N][N];
int n;

queue<int> q;
map<int,int> path;


int merge(int x, int y) {
	return x * 10000 + y;
}

int getX(int t) {
	return t / 10000;
}

int getY(int t) {
	return t % 10000;
}

int addx[] = { 1,0,-1,0 };
int addy[] = { 0,1,0,-1 };

void printpath() {
	vector<int> ans;
	int x = n - 1; int y = n - 1;
	ans.push_back(x); ans.push_back(y);

	while (x != 0 || y != 0) {
		int next = path[merge(x, y)];
		x = getX(next); y = getY(next);
		ans.push_back(x); ans.push_back(y);
	}

	for (int i = ans.size()-1; i >=0 ; i -= 2) {
		cout << ans[i-1] << " " << ans[i] << endl;
	}

	return;
}



int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> gra[i][j];
		}
	}

	q.push(merge(0, 0));
	path[merge(0, 0)] =  0;
	gra[0][0] =1;

	while (!q.empty()) {
		int curr = q.front(); q.pop();
		int x = getX(curr); int y = getY(curr);

		if (x == n - 1 && y == n - 1) {
			printpath();
			return 0; 
		}

		for (int i = 0; i < 4; i++) {
			int newx = x + addx[i];
			int newy = y + addy[i];

			if (newx >= 0 && newx < n && newy>=0 && newy < n && gra[newx][newy] == 0) {
				q.push(merge(newx, newy));
				path[merge(newx, newy)] = merge(x,y);
				gra[newx][newy] = 1;
			}
		}
	}


	return 0;
}

 